#include <stdio.h>

void swap(int* left, int* right)
{
    int tmp = *right;
    *right = *left;
    *left = tmp;
}

//霍尔法
int ParSort_1(int* arr, int left, int right)
{
    int key = left;
    while(left < right)
    {
        while(left < right&&arr[right] >= arr[key]){right--;}
        while(left < right&&arr[left] <= arr[key]){left++;}
        if(left < right)
        swap(&arr[left], &arr[right]);
    }

    swap(&arr[key], &arr[left]);
    return left;
}

//挖坑法
int ParSort_2(int* arr, int left, int right)
{
    int key = arr[left];
    int hole = left;

    while(left < right)
    {
        while(left < right&&arr[right] >= key){right--;}
        arr[hole] = arr[right];
        hole = right;

        while(left < right&&arr[left] <= key){left++;}
        arr[hole] = arr[left];
        hole = left;
    }

    arr[hole] = key;
    return hole;
}

//前后指针
int ParSort_3(int* arr, int left, int right)
{
    int key = left;
    int prev = left;
    int cur = left + 1;
    while(cur <= right)
    {
        //arr[cur]小于基准值就交换
        if(arr[cur] <= arr[key]&&++prev != cur)
        {
            swap(&arr[prev], &arr[cur]);
        }
        cur++;
    }

    swap(&arr[key], &arr[prev]);
    return prev;
}

//快速排序
void QuickSort(int* arr, int begin, int end)
{
    if(begin >= end)
    return;

    int key = ParSort_3(arr, begin, end);
    QuickSort(arr, key + 1, end);//排右边
    QuickSort(arr, begin, key - 1);//排左边
}

int main()
{
    int arr[] = {3, 1, 4, 3, 8, 8, 4, 1, 8, 0};
    QuickSort(arr, 0, 9);
    for(int i = 0; i < 10; i++)
    printf("%d ", arr[i]);
    return 0;
}